/*
struct TreeNode {
	int val;
	struct TreeNode *left;
	struct TreeNode *right;
	TreeNode(int x) :
			val(x), left(NULL), right(NULL) {
	}
};*/
#include <cmath>
class Solution {
public:
	vector<TreeNode*> res;
	void dfs(TreeNode* root)
	{
		if (root == nullptr)
			return;
		dfs(root->left);
		res.push_back(root);
		dfs(root->right);
	}
	TreeNode* Convert(TreeNode* pRootOfTree) {
		if (pRootOfTree == nullptr) return nullptr;

		dfs(pRootOfTree);

		for (int i = 0; i < res.size() - 1; ++i)
		{
			res[i]->right = res[i + 1];
		}
		for (int i = 1; i < res.size(); ++i)
		{
			res[i]->left = res[i - 1];
		}
		res.front()->left = nullptr;
		res.back()->right = nullptr;
		return res.front();
	}
};
